// Created by WXX on 2021/11/15 14:03
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
 * 内存消耗：5.8 MB, 在所有 C++ 提交中击败了68.68%的用户
 */
typedef long long LL;

class Solution {
public:
    int preimageSizeFZF(int k) {
        if (k == 0) return 5;
        return calc(k) - calc(k - 1);
    }

    LL f(LL x) {  // x! 末尾零的个数
        LL res = 0;
        while (x) res += x / 5, x /= 5;
        return res;
    }

    int calc(int k) {  // 末尾0的个数小于等于k的阶乘的数量
        LL l = 0, r = 1e18;
        while (l < r) {
            LL mid = l + r + 1 >> 1;
            if (f(mid) <= k) l = mid;
            else r = mid - 1;
        }
        return r;
    }
};

int main() {


    cout << Solution().preimageSizeFZF(0) << endl;  // 5
    cout << Solution().preimageSizeFZF(5) << endl;  // 0

    return 0;
}
